package RealTim0;

// TODO 动态规划 | 完全背包问题 [经典] 【-】 零钱兑换
// TODO https://leetcode.cn/problems/coin-change/solutions/668758/322-ling-qian-dui-huan-dong-tai-gui-hua-e2nt7/

import java.util.Arrays;

public class xqz0004 {

    public int coinChange(int[] coins, int amount) {
        // dp[i]表示 凑齐i元 最少需要多少货币数
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        // 初始状态
        dp[0] = 0;

        // 状态转移
        for(int coin : coins){
            for(int j = coin; j < amount + 1; j++){
                // 维护最小值
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        // 如果最终答案大于 amount 代表无解
        return dp[amount] != 10001 ? dp[amount] : -1;
    }

    public static int minMoney (int[] arr, int aim) {
        // dp[i]表示 凑齐i元 最少需要多少货币数
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);

        // 初始状态
        dp[0] = 0;

        // 状态转移
        for(int i = 1; i <= aim; i++){
            // 每种面值的货币都要枚举
            for(int j = 0; j < arr.length && arr[j] <= i; j++){
                //维护最小值
                dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] > aim ? -1 : dp[aim];
    }

}
